{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Books You Can Take"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #dynamic-programming #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #动态规划 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumBooks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #你能拿走的最大图书数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的<b>&nbsp;下标从 0 开始&nbsp;</b>的整数数组 <code>books</code>，其中 <code>books[i]</code> 表示书架的第 <code>i</code> 个书架上的书的数量。</p>\n",
    "\n",
    "<p>你要从书架&nbsp;<code>l</code> 到 <code>r</code> 的一个&nbsp;<strong>连续&nbsp;</strong>的部分中取书，其中 <code>0 &lt;= l &lt;= r &lt; n</code>。对于 <code>l &lt;= i &lt; r</code> 范围内的每个索引 <code>i</code>，你从书架 <code>i</code>&nbsp;取书的数量必须&nbsp;<strong>严格小于 </strong>你从书架 <code>i + 1</code> 取书的数量。</p>\n",
    "\n",
    "<p>返回<em>你能从书架上拿走的书的&nbsp;<strong>最大&nbsp;</strong>数量。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> books = [8,5,2,7,9]\n",
    "<strong>输出:</strong> 19\n",
    "<strong>解释:</strong>\n",
    "- 从书架 1 上取 1 本书。\n",
    "- 从书架 2 上取 2 本书。\n",
    "- 从书架 3 上取 7 本书\n",
    "- 从书架 4 上取 9 本书\n",
    "你已经拿了19本书，所以返回 19。\n",
    "可以证明 19 本是你所能拿走的书的最大数量。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> books = [7,0,3,4,5]\n",
    "<strong>输出:</strong> 12\n",
    "<strong>解释:</strong>\n",
    "- 从书架 2 上取 3 本书。\n",
    "- 从书架 3 上取 4 本书。\n",
    "- 从书架 4 上取 5 本书。\n",
    "你已经拿了 12 本书，所以返回 12。\n",
    "可以证明 12 本是你所能拿走的书的最大数量。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> books = [8,2,3,7,3,4,0,1,4,3]\n",
    "<strong>输出:</strong> 13\n",
    "<strong>解释:</strong>\n",
    "- 从书架 0 上取 1 本书。\n",
    "- 从书架 1 上取 2 本书。\n",
    "- 从书架 2 上取 3 本书。\n",
    "- 从书架 3 上取 7 本书。\n",
    "你已经拿了 13 本书，所以返回 13。\n",
    "可以证明 13 本是你所能拿走的书的最大数量。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= books.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= books[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-books-you-can-take](https://leetcode.cn/problems/maximum-number-of-books-you-can-take/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-books-you-can-take](https://leetcode.cn/problems/maximum-number-of-books-you-can-take/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,5,2,7,9]', '[7,0,3,4,5]', '[8,2,3,7,3,4,0,1,4,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        # 单调栈记录id，以id结尾的书最多取几本\n",
    "        # 每到一个新的id，若books[id]比book[id-1]大，dp[id] = dp[id-1]+books[id]\n",
    "        # 否则，从栈开始弹出直到满足栈顶id对应的book比当前id小，栈顶id到当前id这一段是等差数列，求和后加上dp[栈顶id]\n",
    "        # 为什么中间的可以弹出，因为books[当前id]决定了这些数字之后不会用到了\n",
    "        s = [(-1, 0)]\n",
    "        ans = 0\n",
    "        n = len(books)\n",
    "        for i in range(n):\n",
    "            while len(s) > 1 and books[s[-1][0]] - s[-1][0] >= books[i] - i:\n",
    "                s.pop()\n",
    "            size = min(i - s[-1][0], books[i])\n",
    "            t = (2 * books[i] - size + 1) * size // 2 + s[-1][1]\n",
    "            ans = max(ans, t)\n",
    "            s.append((i, t))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        sk = [(-1,-inf,0)]\n",
    "        res = 0\n",
    "        for i,a in enumerate(books):\n",
    "            while sk[-1][1]>=a-i:\n",
    "                sk.pop()\n",
    "            w = min(i-sk[-1][0],a)\n",
    "            s = sk[-1][2]+(2*a-w+1)*w//2\n",
    "            sk.append((i,a-i,s))\n",
    "            res = max(res,s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        ans, st = 0, [(-1, 0)]\n",
    "        for i, v in enumerate(books):\n",
    "            while len(st) > 1 and books[st[-1][0]] - st[-1][0] >= v - i:\n",
    "                st.pop()\n",
    "            size = min(i - st[-1][0], v)\n",
    "            s = (v * 2 - size + 1) * size // 2 + st[-1][1]\n",
    "            ans = max(ans, s)\n",
    "            st.append((i, s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        ans, st = 0, [(-1, 0)]  # 单调栈里面存 (下标, dp 值)，加个哨兵\n",
    "        for i, v in enumerate(books):\n",
    "            while len(st) > 1 and books[st[-1][0]] - st[-1][0] >= v - i:\n",
    "                st.pop()\n",
    "            size = min(i - st[-1][0], v)\n",
    "            s = (v * 2 - size + 1) * size // 2 + st[-1][1]\n",
    "            ans = max(ans, s)\n",
    "            st.append((i, s))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        ans, st = 0, [(-1, 0)]  # 单调栈里面存 (下标, dp 值)，加个哨兵\n",
    "        for i, v in enumerate(books):\n",
    "            while len(st) > 1 and books[st[-1][0]] - st[-1][0] >= v - i:\n",
    "                st.pop()\n",
    "            size = min(i - st[-1][0], v)\n",
    "            s = (v * 2 - size + 1) * size // 2 + st[-1][1]\n",
    "            ans = max(ans, s)\n",
    "            st.append((i, s))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n=len(books)\n",
    "        dp=[0]*n#以每个书架为右边间可以拿的书的数量\n",
    "        ls=[]#单调栈\n",
    "        for i,b in enumerate(books):\n",
    "            #如果这个书架的书数量>=当前书架依次递减一本的数量\n",
    "            #如果这个书架是不会制约从当前书架的依次减少一本往前拿的\n",
    "            while ls and books[ls[-1]]>=b-(i-ls[-1]):\n",
    "                ls.pop()\n",
    "            #栈空说明前面都满足或者是前面没有\n",
    "            if not ls:\n",
    "                #最多可以递减往前的书架是取决于 当前书架位置和书架书本数量的最小值\n",
    "                t=min(i+1,b)\n",
    "                #计算可以拿多少本\n",
    "                dp[i]=(b-t+1+b)*t//2\n",
    "            else:\n",
    "                #最多可以递减往前的书架是取决于 \n",
    "                #制约递减书架位置到当前书架的距离 当前书架位置和书架书本数量的最小值\n",
    "                t=min(i-ls[-1],b)\n",
    "                #计算可以依次递减多少本 加上制约书架往前可以拿的书\n",
    "                dp[i]=(b-t+1+b)*t//2+dp[ls[-1]]\n",
    "            ls.append(i)\n",
    "        return max(dp)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n=len(books)\n",
    "        dp=[0]*n\n",
    "        ls=[]\n",
    "        for i,b in enumerate(books):\n",
    "            while ls and books[ls[-1]]>=b-(i-ls[-1]):\n",
    "                ls.pop()\n",
    "            if not ls:\n",
    "                t=min(i+1,b)\n",
    "                l=b-t+1\n",
    "                s=(l+b)*t//2\n",
    "                dp[i]=s\n",
    "            else:\n",
    "                t=min(i-ls[-1],b)\n",
    "                l=b-t+1\n",
    "                s=(l+b)*t//2\n",
    "                dp[i]=s+dp[ls[-1]]\n",
    "            ls.append(i)\n",
    "        return max(dp)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n = len(books)\n",
    "\n",
    "        dp = [0]*n\n",
    "        stack = [(books[0],0)]\n",
    "        dp[0] = books[0]\n",
    "\n",
    "        ans = books[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "\n",
    "            xi = books[i]-i\n",
    "            yi = books[i]\n",
    "\n",
    "            while stack and stack[-1][0]>=xi:\n",
    "                stack.pop()\n",
    "\n",
    "            if not stack:\n",
    "                if yi>i+1:\n",
    "                    dp[i] = ((yi+yi-i)*(i+1))//2\n",
    "                if yi<=i+1:\n",
    "                    dp[i] = ((yi+1)*yi)//2\n",
    "                \n",
    "                stack.append( (xi,i))\n",
    "\n",
    "                ans = max(ans,dp[i])\n",
    "                continue \n",
    "\n",
    "            val, j = stack[-1]\n",
    "            dp[i] = dp[j]+((books[i]+books[i]-(i-j)+1 )*(i-j))//2\n",
    "            stack.append((xi,i))\n",
    "\n",
    "            ans = max(ans,dp[i])\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n=len(books)\n",
    "        dp=[0]*n#以每个书架为右边间可以拿的书的数量\n",
    "        ls=[]#单调栈\n",
    "        for i,b in enumerate(books):\n",
    "            #如果这个书架的书数量>=当前书架依次递减一本的数量\n",
    "            #这个书架是不会制约从当前书架的依次减少一本往前拿的\n",
    "            while ls and books[ls[-1]]>=b-(i-ls[-1]):\n",
    "                ls.pop()\n",
    "            #栈空说明前面都满足或者是前面没有\n",
    "            if not ls:\n",
    "                #最多可以递减往前的书架是取决于 当前书架位置和书架书本数量的最小值\n",
    "                t=min(i+1,b)\n",
    "                #计算可以拿多少本\n",
    "                dp[i]=(b-t+1+b)*t//2\n",
    "            else:\n",
    "                #最多可以递减往前的书架是取决于 \n",
    "                #制约递减书架位置到当前书架的距离 当前书架位置和书架书本数量的最小值\n",
    "                t=min(i-ls[-1],b)\n",
    "                #计算可以依次递减拿的数量 加上制约书架往前可以拿的书\n",
    "                dp[i]=(b-t+1+b)*t//2+dp[ls[-1]]\n",
    "            ls.append(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n=len(books)\n",
    "        dp=[0]*n#以每个书架为右边间可以拿的书的数量\n",
    "        ls=[]#单调栈\n",
    "        for i,b in enumerate(books):\n",
    "            #如果这个书架的书数量>=当前书架依次递减一本的数量\n",
    "            #如果这个书架是不会制约从当前书架的依次减少一本往前拿的\n",
    "            while ls and books[ls[-1]]>=b-(i-ls[-1]):\n",
    "                ls.pop()\n",
    "            #栈空说明前面都满足或者是前面没有\n",
    "            if not ls:\n",
    "                #最多可以递减往前的书架是取决于 当前书架位置和书架书本数量的最小值\n",
    "                t=min(i+1,b)\n",
    "                #计算可以拿多少本\n",
    "                dp[i]=(b-t+1+b)*t//2\n",
    "            else:\n",
    "                #最多可以递减往前的书架是取决于 \n",
    "                #制约递减书架位置到当前书架的距离 当前书架位置和书架书本数量的最小值\n",
    "                t=min(i-ls[-1],b)\n",
    "                #计算可以依次递减多少本 加上制约书架往前可以拿的书\n",
    "                dp[i]=(b-t+1+b)*t//2+dp[ls[-1]]\n",
    "            ls.append(i)\n",
    "        return max(dp)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://www.bilibili.com/video/BV1PG411n7FS/\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        dp = [0] * len(books)\n",
    "        stk = []\n",
    "        for i in range(len(books)):\n",
    "            while stk and books[stk[-1]] >= books[i] - (i - stk[-1]):\n",
    "                stk.pop()\n",
    "\n",
    "            if stk:\n",
    "                j = stk[-1]\n",
    "                L = i - j\n",
    "                dp[i] = dp[j] + (books[i] + books[i] - L + 1) * L\n",
    "            else:\n",
    "                L = min(i + 1, books[i])\n",
    "                dp[i] = (books[i] + books[i] - L + 1) * L\n",
    "                \n",
    "            stk.append(i)\n",
    "        return max(dp) >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n=len(books)\n",
    "        dp=[0]*n\n",
    "        ls=[]\n",
    "        for i,b in enumerate(books):\n",
    "            while ls and books[ls[-1]]>=b-(i-ls[-1]):\n",
    "                ls.pop()\n",
    "            if not ls:\n",
    "                t=min(i+1,b)\n",
    "                l=b-t+1\n",
    "                s=(l+b)*t//2\n",
    "                dp[i]=s\n",
    "            else:\n",
    "                t=min(i-ls[-1],b)\n",
    "                l=b-t+1\n",
    "                s=(l+b)*t//2\n",
    "                dp[i]=s+dp[ls[-1]]\n",
    "            ls.append(i)\n",
    "        return max(dp)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n=len(books)\n",
    "        dp=[0]*n#以每个书架为右边间可以拿的书的数量\n",
    "        ls=[]#单调栈\n",
    "        res=0\n",
    "        for i,b in enumerate(books):\n",
    "            #如果这个书架的书数量>=当前书架依次递减一本的数量\n",
    "            #如果这个书架是不会制约从当前书架的依次减少一本往前拿的\n",
    "            while ls and books[ls[-1]]>=b-(i-ls[-1]):\n",
    "                ls.pop()\n",
    "            #栈空说明前面都满足或者是前面没有\n",
    "            if not ls:\n",
    "                #最多可以递减往前的书架是取决于 当前书架位置和书架书本数量的最小值\n",
    "                t=min(i+1,b)\n",
    "                #计算可以拿多少本\n",
    "                dp[i]=(b-t+1+b)*t//2\n",
    "            else:\n",
    "                #最多可以递减往前的书架是取决于 \n",
    "                #制约递减书架位置到当前书架的距离 当前书架位置和书架书本数量的最小值\n",
    "                t=min(i-ls[-1],b)\n",
    "                #计算可以依次递减多少本 加上制约书架往前可以拿的书\n",
    "                dp[i]=(b-t+1+b)*t//2+dp[ls[-1]]\n",
    "            ls.append(i)\n",
    "            res=max(res,dp[i])\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n = len(books)\n",
    "\n",
    "        dp = [0]*n\n",
    "        stack = [(books[0],0)]\n",
    "        dp[0] = books[0]\n",
    "\n",
    "        firstJ = [-1]*n\n",
    "        for i in range(1,n):\n",
    "            xi = books[i]-i\n",
    "            while stack and stack[-1][0]>=xi:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                stack.append((xi,i))\n",
    "            else:\n",
    "                firstJ[i] = stack[-1][1]\n",
    "                stack.append((xi,i))\n",
    "\n",
    "\n",
    "        for i in range(1,n):\n",
    "\n",
    "            j = firstJ[i]\n",
    "\n",
    "            count = min(i-j,books[i]) \n",
    "            first, last = max(1, books[i]-(i-j)+1 ) ,books[i]\n",
    "\n",
    "            sum_i = (first+last)*count//2\n",
    "            dp[i] = sum_i + (dp[j] if j!=-1 else 0)\n",
    "            \n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBooks(self, books: List[int]) -> int:\n",
    "        n = len(books)\n",
    "\n",
    "        dp = [0]*n\n",
    "        stack = [(books[0],0)]\n",
    "        dp[0] = books[0]\n",
    "\n",
    "        firstJ = [-1]*n\n",
    "        for i in range(1,n):\n",
    "            xi = books[i]-i\n",
    "            while stack and stack[-1][0]>=xi:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                stack.append((xi,i))\n",
    "            else:\n",
    "                firstJ[i] = stack[-1][1]\n",
    "                stack.append((xi,i))\n",
    "\n",
    "\n",
    "        for i in range(1,n):\n",
    "\n",
    "            j = firstJ[i]\n",
    "\n",
    "            count = min(i-j,books[i]) \n",
    "            first, last = max(1, books[i]-count+1 ) ,books[i]\n",
    "\n",
    "            sum_i = (first+last)*count//2\n",
    "            dp[i] = sum_i + (dp[j] if j!=-1 else 0)\n",
    "            \n",
    "        return max(dp)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
